package leetcode.editor.cn.q1_300.q50;

/**
 * @author qidi
 * @date 2021-12-09 10:26:47
 */
class Q0053_MaximumSubarray {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxSubArray(int[] nums) {
            int maxSum = -10000;

            int curSum = -10000;

            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > curSum + nums[i]) {
                    curSum = nums[i];
                } else {
                    curSum += nums[i];
                }
                maxSum = Math.max(maxSum, curSum);
            }
            return maxSum;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0053_MaximumSubarray().new Solution();
        System.out.println(solution.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
        System.out.println(solution.maxSubArray(new int[]{5, 4, -1, 7, 8}));
    }
}